﻿using System;
using System.Collections.Generic;
using System.Linq;
using MartinRL.ProjectEuler.Sequences;

namespace MartinRL.ProjectEuler
{
    /// <summary>
    /// http://projecteuler.net/index.php?section=problems&id=14
    /// </summary>
    public static class Problem014
    {
        public static int FindTheStartingNumberUnderOneMillionThatProducesTheLongestChain()
        {
            return 2.To(999999)
                .Select(t => new {
                                     Term = t,
                                     ChainLength = CalculateLengthFor(t)
                                 })
                .OrderByDescending(tc => tc.ChainLength)
                .First().Term;
        }

        public static long CalculateLengthFor(long startTerm)
        {
            var uncachedCollatzSequence = GetUncachedCollatzSequence(startTerm);

            if (uncachedCollatzSequence.Any())
            {
                AddUncachedLengthValuesToCache(uncachedCollatzSequence);
            }

            return _cache[startTerm];
        }

        private static void AddUncachedLengthValuesToCache(IEnumerable<long> uncachedCollatzSequence)
        {
            var lastInCollatzSequence = uncachedCollatzSequence.Last();
            var lengthAddition = 0;
            var collatzSequenceLength = uncachedCollatzSequence.Count();

            if (lastInCollatzSequence != 1)
            {
                var nextTerm = CollatzSequence.CollatzEnumerator.CalculateNext(lastInCollatzSequence);

                lengthAddition = _cache[nextTerm];
            }

            uncachedCollatzSequence
                .Select((t, i) => new {Term = t, Length = collatzSequenceLength - i + lengthAddition})
                .ForEach(tl => _cache.Add(tl.Term, tl.Length));
        }

        private static IEnumerable<long> GetUncachedCollatzSequence(long startTerm)
        {
            return CollatzSequence.NewSequence(startTerm)
                .TakeWhile(t => !_cache.ContainsKey(t));
        }

        private static readonly IDictionary<long, int> _cache = new Dictionary<long, int>();
    }
}